package 字节;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class 三数之和 {
    static public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);

        return three(nums,3,0,0);

    }
    static List<List<Integer>> three(int[] nums,int n,int start,int sum){
        List<List<Integer>> res=new LinkedList<>();
        if(n<2||n>nums.length) return res;
        if(n==2){
            int lo=start;
            int hi=nums.length-1;
            while (lo<hi){
                int sum0=nums[lo]+nums[hi];
                int left=nums[lo];
                int right=nums[hi];
                if(sum0<sum){
                    while (lo<hi&&nums[lo]==left) lo++;
                }else if(sum0>sum){
                    while (lo<hi&&nums[hi]==right) hi--;
                }else {
                    List<Integer> list=new LinkedList<>();
                    list.add(left);
                    list.add(right);
                    res.add(list);
                    while (lo<hi&&nums[lo]==left) lo++;
                    while (lo<hi&&nums[hi]==right) hi--;
                }
            }
        }else {
            for (int i=0;i<nums.length;i++){
                List<List<Integer>> res1=three(nums,n-1,i+1,sum-nums[i]);
                for (List<Integer> list : res1) {
                    list.add(nums[i]);
                    res.add(list);
                }
                while(i<nums.length-1&&nums[i]==nums[i+1]) i++;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums={-1,0,1,2,-1,-4};
        List<List<Integer>> res=threeSum(nums);
        for (List<Integer> re : res) {
            for (Integer integer : re) {
                System.out.print(integer+",");
            }
            System.out.println();
        }
    }
}
